package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
 * Find all unique triplets in the array which gives the sum of zero.
 * Example:
 * given array S = [-1, 0, 1, 2, -1, -4],
 * A solution set is:
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 */
public class Sum3 {

    public static void main(String[] args) {
        int[] s = {-1, 0, 0, 0, 1, 2, -1, -4, -1};
        List<List<Integer>> lists = threeSum(s);
        System.out.println(lists);
    }

    private static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);

        System.out.println(Arrays.toString(nums));
        for (int start = 0; start < nums.length - 2; start++) {

            if (start != 0 && nums[start - 1] == nums[start]) {
                continue;
            }

            int mid = start + 1;
            int end = nums.length - 1;

            while (mid < end) {
                int sum = nums[start] + nums[mid] + nums[end];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[start]);
                    list.add(nums[mid]);
                    list.add(nums[end]);
                    res.add(list);

                    do {
                        ++mid;
                    } while(mid < end && nums[mid - 1] == nums[mid]);

                    do {
                        --end;
                    } while(mid < end && nums[end + 1] == nums[end]);

//                    运行异常
//                    while (nums[mid] == nums[mid + 1] && mid + 1 < end) {
//                        mid++;
//                    }
//                    while (nums[end] == nums[end - 1] && mid < end - 1) {
//                        end--;
//                    }
                } else if (sum > 0) {
                    end--;
                } else {
                    mid++;
                }
            }
        }
        return res;
    }
}
